/***
 * 斐波那契数列求和
 * 1 1 2 3 5...
 */

#include <chrono>
#include <iostream>

using namespace std;
using namespace std::chrono;

// 时间复杂度O(n^2)
int func1(int n) {
    if (n <= 0)
        return 0;
    if (n == 1)
        return 1;

    return func1(n - 1) + func1(n - 2);
}

// 时间复杂度O(n)
int func2(int first, int second, int n) {
    if (n <= 0)
        return 0;
    if (n < 3)
        return 1;
    else if (n == 3) {
        return first + second;
    } else {
        int result = func2(second, first + second, n - 1);
        return result;
    }
}

int main() {
    int n;
    while (1) {
        cout << "cin n: " << endl;
        cin >> n;

        auto startTime = high_resolution_clock::now();
        int result = func2(1, 1, n);
        auto endTime = high_resolution_clock::now();

        auto duration = duration_cast<milliseconds>(endTime - startTime);
        cout << "cost time: " << duration.count() << " ms" << endl;
        cout << "result = " << result << endl;
    }

    system("pause");
    return 0;
}